package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-11-19 15:04:37
 */
class Q0041_FirstMissingPositive {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int firstMissingPositive(int[] nums) {
            // ��ΪҪ����С������˵���� 1 ~ nums.length ��Χ��һ�����ڲ�������Ҳ����˵ ���һ���� �����Χ�ڳ��� �ϳ���
            boolean[] flags = new boolean[nums.length + 2];

            flags[0] = true;
            for (int num : nums) {
                if (num > 0 && num < nums.length + 2) flags[num] = true;
            }

            for (int i = 0; i < flags.length; i++) {
                if (!flags[i]) return i;
            }

            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0041_FirstMissingPositive().new Solution();
        System.out.println(solution.firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(solution.firstMissingPositive(new int[]{3, 4, -1, 1}));
        System.out.println(solution.firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
        System.out.println(solution.firstMissingPositive(new int[]{1}));
    }
}